N = 2500;
T = [1746,1882,1083,1939,2468,1102,2317,1273,1572,962,842,2392,1543,2418,1390,300,1682,926,1619,2155,162,1488,180,459,128,2402,2405,1661,1714,383,1909,202,712,683,1050,2095,1060,1212,647,1278,981,773,338,1045,2499,1918,427,1263,817,1468,714,599,2475,4,2489,911,2173,2026,1080,2113,1734,1806,1288,1141,857,571,2038,1223,847,2411,531,1607,2210,1000,2380,1302,1935,1457,214,2092,1629,1656,352,1910,2351,205,1562,1692,1328,1244,141,705,996,1046,1813,771,1853,2445,515,1704,1362,998,1085,1032,969,989,2389,296,1590,1350,372,317,2103,1144,394,2393,1466,1117,1972,2203,717,1381,536,1576,1964,351,112,1817,1098,200,2407,1088,2257,2254,743,834,2114,1677,458,187,428,2144,623,366,450,2236,1240,1028,584,2190,217,1867,239,2397,1161,2029,1782,500,718,103,1441,263,1428,1641,887,1002,1435,206,308,160,2437,1077,631,540,658,1428,158,723,732,696,1271,49,1307,2294,1413,2478,613,1869,1355,2250,1577,232,1289,867,1378,762,2067,1745,2459,2196,2218,322,1756,951,1840,2275,115,309,1533,2087,659,121,2481,1747,541,218,225,243,704,1736,1821,532,1198,330,1551,53,1508,2125,158,1063,2129,612,198,2357,1709,2109,2091,838,1922,1546,2187,1684,2189,1481,2417,892,2300,2116,391,2467,1900,2065,720,1489,476,643,973,28,2284,2178,1660,398,1768,1268,332,275,687,482,886,723,1578,1872,597,411,1925,2143,120,1878,798,1372,565,1159,1663,193,352,1915,651,1798,1608,1609,325,265,273,1981,853,792,2323,2141,1279,570,1465,216,1575,475,684,1668,1464,1497,173,2377,2409,264,1883,2027,1121,768,991,1473,179,1199,1673,572,863,1179,809,1890,1471,602,1724,2469,421,1672,1681,1398,2487,76,1158,1951,37,61,1168,840,294,370,2217,829,15,109,1190,318,766,178,1114,544,492,1921,850,1491,2197,374,1099,2092,1948,34,2158,315,1554,569,1584,171,2347,964,817,2443,1962,1848,1814,135,876,1396,1221,985,2227,340,1800,83,546,1718,1469,2353,881,2015,3,12,2136,547,1881,1040,119,489,2344,1412,938,203,1650,1020,286,463,2267,263,1353,310,143,1757,1088,2198,219,2423,935,226,167,64,347,2248,24,947,1454,2060,1530,624,129,1363,2473,1528,1437,1003,1058,646,836,739,423,1690,1736,1837,1703,559,1746,1539,126,1996,1150,298,1891,1108,1499,2311,2233,845,551,1057,1513,1775,1100,460,2486,1920,1642,390,663,1423,1449,1777,1722,356,1237,2245,2436,2273,1418,437,1196,1689,2477,1054,2213,152,1451,1864,811,400,2490,1301,2486,1908,2167,41,787,1120,2097,2333,2161,2046,1456,1914,1766,625,183,186,673,591,763,240,2458,1147,2156,1376,764,1797,1542,2030,1694,858,1574,1091,1116,1330,1772,371,1195,2470,441,1643,353,2158,675,638,1365,1217,99,1460,1291,1659,851,689,2244,1299,1723,1342,2114,1531,703,1624,947,2242,1146,1822,1623,436,1593,1786,1368,2176,445,751,207,377,2201,539,869,166,346,1716,700,1594,8,199,1139,2098,784,95,306,175,1216,188,1579,481,2068,293,2382,150,749,2018,1829,1157,143,1148,1187,1001,1308,204,1928,2135,1026,1517,2020,2334,1842,791,223,387,2446,2130,1828,1057,1679,1210,1825,1593,232,1394,697,469,1942,486,1860,2246,1824,1089,160,2022,2093,56,108,1566,217,1665,662,187,771,1978,695,1895,1538,1884,104,302,1443,1482,1165,2209,1601,1633,2261,686,737,795,1358,1985,164,888,622,473,384,781,1094,1874,456,872,916,1892,1525,1582,1687,1944,1929,1227,1553,827,1611,2254,1898,880,927,2491,1053,1254,812,1264,904,1346,1849,1481,221,895,1047,1795,1919,2399,609,2374,70,1126,903,132,2216,1805,16,840,341,1662,849,321,1087,174,2001,2454,149,801,1203,813,545,1843,1744,1598,1490,11,284,1048,425,1744,1712,810,98,2002,2354,1424,213,690,431,789,142,803,86,1065,123,1176,1136,1029,2195,2394,2341,71,278,418,1284,1070,1765,2053,1001,2239,1056,1857,660,2379,231,81,1561,2149,1565,2257,447,752,2138,1502,1290,290,1332,1516,266,1281,1610,73,1580,1164,2432,2046,1095,1495,1429,403,1771,354,706,2152,2384,467,485,211,1933,1356,35,1320,2234,33,1820,2255,548,2120,528,1256,1427,761,2492,1407,1819,2043,1976,430,974,10,230,401,641,249,1889,1955,1979,1519,1847,1239,247,1200,2358,2361,1701,2117,1265,775,630,404,2426,1205,1022,356,509,1005,1129,402,562,1547,1832,1965,477,777,915,2318,350,292,1345,2021,691,1773,742,481,1728,1207,1833,334,503,348,1868,1839,821,1461,1403,1635,1225,1023,1862,1305,79,1393,843,2160,882,526,1370,774,514,949,1591,1627,375,1143,2147,1545,1763,1025,934,438,1014,567,268,38,1595,194,257,479,2500,1941,364,1729,1352,1478,1646,147,633,1201,1846,2051,815,2298,1226,2327,1106,1785,421,2380,66,2263,2059,2163,2314,556,1871,1897,2204,2041,1208,60,1142,184,1375,250,2231,14,1137,381,87,948,1683,2238,1392,2456,1740,1456,426,785,2005,688,1224,2047,2240,1552,2230,1151,339,1128,31,2279,2209,466,976,561,1612,1371,1540,2094,1927,1286,65,262,2271,2326,1109,764,2082,921,1781,1246,929,489,942,2078,778,1906,1335,110,1133,324,1706,2479,941,800,2236,117,945,2070,2449,1835,2132,1274,1252,1518,474,2325,841,1666,452,1748,1711,382,1036,2421,2119,664,1774,323,656,138,340,1361,769,513,535,2308,2021,1111,543,984,820,862,333,2123,1779,329,143,1713,2140,1537,2170,1765,1992,42,21,2079,1294,2126,720,481,1511,2395,1034,1578,1303,2419,2081,627,163,1079,237,2154,2252,1123,2302,794,1181,1071,1158,669,1693,566,1500,101,1349,1051,874,1770,58,118,1780,483,2302,1512,1134,2461,852,1248,1534,44,1041,1688,1548,1899,848,1082,860,2008,797,1351,1322,1055,1247,1645,2279,23,914,1596,1262,2215,2474,1910,1573,936,1493,30,244,1787,2368,1702,1680,1081,687,891,2385,756,626,2165,353,1038,1674,2206,227,1037,2331,819,1389,57,181,2016,168,173,681,122,1241,2154,1834,62,1796,2088,1397,208,1717,2212,334,313,1249,1520,1138,159,828,575,541,2037,551,682,1945,1432,286,385,1850,1388,2353,846,1188,1863,1830,2472,1149,153,1890,747,535,1421,1319,1325,628,653,1527,1653,754,1203,2229,470,2270,201,63,2074,2075,295,269,2082,2293,1374,511,1622,1338,19,1604,77,259,997,896,2373,772,399,770,424,1802,863,2372,982,632,1017,1609,480,1854,1749,1581,596,2180,1342,714,1911,1463,50,2378,1315,581,2294,2153,39,1647,2404,297,11,22,1496,2340,2343,40,1875,668,2243,136,2182,1865,472,524,1648,417,966,1167,1815,2266,148,629,1169,1654,2058,261,2396,280,2220,731,242,1010,2444,506,2115,1431,167,392,1989,1155,905,2296,900,2235,653,1417,1764,363,1197,1558,1568,932,1758,1238,1477,793,147,1194,1705,2003,2299,605,490,1184,1251,854,2322,2,1510,1285,603,2169,2200,831,224,1615,1367,907,1010,2435,791,1030,2329,523,2029,1380,252,970,1364,806,328,908,1969,1440,832,1009,1571,1973,1206,1480,155,2178,1064,808,1147,2306,1369,1845,2316,47,2274,127,2365,1269,1215,2267,1851,2442,454,1657,1110,257,2085,1877,978,1078,1670,1282,939,1004,2288,676,637,487,67,105,1750,2463,1484,133,1894,1324,2127,1075,1399,959,1793,1631,594,1453,1982,925,1823,1483,558,434,1652,1347,1306,1672,1966,680,640,1061,2148,69,2473,990,2121,790,1297,654,319,499,2056,786,235,443,1563,1772,2438,1450,592,512,301,1776,6,1903,1140,1980,755,1236,2496,2390,522,1621,27,856,1984,1974,46,955,43,1967,2281,1861,1445,957,254,783,2142,564,1259,2337,870,210,1596,616,380,195,1438,2211,681,1962,1276,1321,814,2320,1667,1018,550,251,693,901,2177,1671,229,1905,740,1258,1769,1472,733,520,603,2356,1101,311,61,644,1503,1657,585,91,2113,1913,1162,434,72,1707,1501,1561,2494,55,748,2312,930,1234,349,744,1125,2167,2017,20,2063,1636,274,2000,707,1097,830,107,609,1211,464,303,1150,1218,2304,2345,1739,807,873,393,344,652,1467,2338,144,1225,89,1386,1238,1594,657,1655,2209,2335,284,388,1544,1904,950,32,1769,897,1521,1132,1600,802,2274,429,746,29,1799,977,2019,498,376,666,439,1308,1726,902,1761,1873,1605,1420,2466,1506,457,2346,1277,1487,95,1498,2381,871,672,1049,1676,26,327,1735,1816,2291,645,1257,1742,7,2145,1144,2040,643,944,2398,952,1076,215,2279,1585,2013,1280,2055,2010,2277,1721,879,2010,961,1599,1285,1522,2098,1092,2193,2226,2462,1455,1818,1359,1209,2262,1789,710,2487,2162,241,453,2128,2289,1856,379,582,2450,1012,1135,1664,307,182,604,88,1381,1228,2397,2133,504,636,1124,85,1311,1773,1017,139,2194,1986,918,1536,1444,1401,1354,2364,1901,1219,1514,1638,521,2298,1287,496,228,1180,2412,1385,1245,1222,898,885,525,1997,1410,90,602,191,843,1044,1639,866,1096,694,97,1618,2440,369,1695,1383,1702,1339,2179,1459,1559,218,587,1535,1753,1225,1298,755,1958,1343,2032,1790,1949,906,738,600,1944,1827,1166,2500,2145,1634,721,1743,1341,716,1583,835,601,1523,701,1613,2150,2303,54,2106,972,2416,185,2191,448,760,277,1408,2159,1202,899,285,1998,283,753,1204,222,2290,1954,884,435,665,2039,649,1755,1628,1859,999,1405,1599,1870,2431,2369,113,1778,2108,1640,1061,2485,2242,698,1321,1404,17,2139,2420,709,516,116,1555,1885,1754,1486,196,1715,1448,2199,2061,728,2455,1024,299,157,1524,360,818,82,478,2042,1185,75,611,1160,568,1876,124,268,2272,2083,1720,949,468,1951,2107,1318,1924,823,1333,2363,577,2146,1532,145,508,1934,2011,396,2260,861,2072,1172,131,790,1313,892,1686,607,2348,1649,822,1896,534,2439,1039,2460,1080,5,420,245,2370,579,1414,1409,2457,172,445,32,560,484,2134,13,1593,491,102,258,1170,1492,1020,661,2184,1947,1331,678,1606,2174,165,2339,1812,2297,1977,561,1113,326,1084,2332,1452,2258,2414,1887,2253,1858,642,320,655,323,537,1669,889,305,668,734,209,2048,114,484,855,2036,1270,2434,190,2309,878,397,1416,1777,1841,828,357,2096,1446,2222,1026,1178,355,246,25,1699,200,1337,2387,2360,10,1826,542,1541,824,1612,1105,1626,2453,1430,1542,963,379,2185,2310,1476,1266,1015,316,432,1734,1402,685,1696,501,74,2228,1680,433,736,1068,920,2352,600,1062,788,1943,965,826,912,121,1991,1314,1458,257,1069,2336,1474,1556,1243,776,448,2186,2110,2313,343,1952,1704,2197,1710,1956,1982,422,1567,958,741,1074,1971,1417,1174,2102,334,2023,2349,488,937,2357,1916,507,1149,2433,364,1260,2064,335,2207,937,2035,2028,314,810,2371,995,2282,2086,471,1391,281,1784,14,2285,859,2131,1494,715,1103,590,677,2144,1644,278,1717,1557,780,1460,1940,1072,2435,2269,1329,1016,2376,2132,1364,1572,125,2473,733,1632,1807,745,45,1938,2396,980,1261,1923,875,2386,1447,1809,1611,80,648,197,804,2251,169,2140,2453,1231,462,943,2367,2054,1529,1073,1406,2480,688,2052,1066,2412,1255,988,2224,272,6,389,2118,573,1730,913,1870,345,1317,442,1193,1272,412,262,1794,1638,1831,2429,1988,1008,1192,1104,2035,1387,233,1993,608,2288,1059,725,2219,1732,414,621,2057,189,77,1968,1719,924,461,1283,2025,994,419,1310,156,865,2151,1384,1810,494,1131,1709,1470,2387,1229,1434,2403,2076,518,1439,1664,557,620,931,1987,1999,1719,1569,1879,839,917,713,1767,379,497,449,1186,1933,1549,2283,395,639,2164,2264,1373,1626,465,1119,1145,946,1293,1914,702,2494,588,2256,2004,1586,425,1214,1108,2388,576,1907,1614,779,2359,2497,1382,1562,2342,2498,972,1760,358,1751,2259,52,2286,1253,1007,282,2099,336,1675,93,248,1589,2391,367,2247,670,2430,722,1113,1127,2177,993,2278,1462,1852,610,1801,36,771,1013,549,634,2315,1836,2,1027,508,1564,538,236,679,617,598,130,1582,1232,750,2164,68,1592,1932,1685,1155,350,1620,2105,288,1151,1960,1738,708,671,440,2221,2476,1603,923,798,1267,1086,405,1302,1752,197,1400,1043,1025,2066,455,1099,164,1392,1383,1588,1388,983,1515,2428,1725,2451,910,1811,2102,456,92,2175,2172,1090,2495,979,78,2122,2374,954,111,1886,893,189,2208,765,615,805,1994,2009,1573,446,1485,2237,160,1880,591,1700,1759,593,1937,967,1475,2006,1788,2100,2166,408,117,18,1019,2333,1436,2012,1327,2376,2314,919,1783,1296,2137,444,1433,1917,2181,635,632,606,587,257,1112,967,2249,312,1979,796,76,837,1805,2447,1426,464,1146,1904,1945,1902,917,1125,2307,238,374,833,2481,1379,968,2124,1067,304,25,2280,291,1804,416,825,552,255,287,724,2425,2049,816,1509,2171,94,1021,1348,572,1122,2465,289,2193,1995,1930,583,1550,505,1304,1213,2295,517,260,619,371,1033,1316,2205,2045,2287,1195,757,530,1808,1737,989,1597,569,2101,894,1560,589,418,2193,2317,735,2471,2069,2460,1697,644,161,782,2072,743,2265,2375,48,711,2427,1602];